package leetcode.doublepoint;

/**
 * 
 * @author 26233
 *
 *给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode142_DetectCycle {
	
	/**
	 * Definition for singly-linked list.
	 */
	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
	ListNode head = null;
	ListNode tail = null;
	
	public LeetCode142_DetectCycle initList(int[] arr) {
		
		for(int i = 0; i < arr.length; i++) {
			if(head == null) {
				head = tail = new ListNode(arr[i]);
				continue;
			}
			
			ListNode newNode = new ListNode(arr[i]);
			tail.next = newNode;
			tail = newNode;
		}
		
		return this;
	}
	
	public ListNode generateCycle(int index) {
		ListNode tempHead = head;
		while(index-- > 0) {
			tempHead = tempHead.next;
		}
		
		tail.next = tempHead;
		
		return head;
	}
	 
	/*
	 * 解法：
	 * 1、快慢指针，p每次移动1,q每次移动2,若存在环,则在环中必会相遇
	 * 2、设链表起点到入环点的距离为d，入环点到相遇点的距离为s1,相遇点到入环点的距离为s2 （s1 + s2 = 环大小）
	 * 3、相遇时有、
	 * 		d1 = d + x*(s1 + s2) + s1
	 * 		d2 = d + n*(s1 + s2) + s2
	 * 
	 * 		d2 = 2 * d1
	 * 
	 * 		d = (n - 2x - 1)(s1 + s2) + s2 
	 * 		n - 2x - 1表示在环中转了多少圈后相遇，假设n-2x-1等于0，因此d=s2
	 * 		d=s2暗示在相遇后，一个指针从环起始点开始每次移动1，一个指针从相遇点开始每次移动1，则他们会在入环点再次相遇
	 * 
	 * 4、相遇点的相等比较：两个指针都移动了之后再比较是否相等
	 */
    public static ListNode detectCycle(ListNode head) {
    	if(head == null) return null;
    	ListNode p = head, q = head;
    	while(q != null) {
    		q = q.next;
    		q = q == null ? null : q.next;
    		p = p.next;
    		if(q == p)break;
    	}
    	if(p == q) {
    		p = head;
    		if(p.next == q) return q;
    		while(p != q) {
    			p = p.next;
    			q = q.next;
    		}
    	}
    	return p == q ? p : null;
    }
    
    public static void main(String[] args) {
		
    	int[] input = {-1,-7,7,-4,19,6,-9,-5,-2,-5};
    	ListNode head = new LeetCode142_DetectCycle().initList(input).generateCycle(6);
    	detectCycle(head);
    	
    	System.out.println("hold");
    	
	}

}
